Error correcting codes are developed for providing a protection of data against errors that are introduced during data transmission or storage due to noise and/or interference. The protection of data consists in adding redundant data to the original data enabling the detection and/or the correction of errors.
Various devices and systems used for data storage or transmission implement error correcting codes for ensuring a reliable and possibly error-free transfer of data in the presence of noisy transfer media. Exemplary applications comprise voice and multimedia transfer for example in wireless ad-hoc networks (e.g. standardized in Wi-Fi 802.11), in radio communication systems (e.g. in 3G, 4G/LTE, 5G and beyond, etc.), in optical communication systems, and in digital video broadcasting (e.g. standardized in DVB-C2, DVB-S2X, and DVB-T2).
Existing error correcting codes comprise linear codes, generally categorized into linear block codes and convolutional codes. Linear codes refer to codes that satisfy a linearity property according to which any linear combination of codeword vectors is a codeword vector. Linear block codes are widely used because they are less complex and easier to implement than non-linear codes. Exemplary linear block codes comprise Hamming codes, Reed-Solomon codes, Turbo codes and low-density parity-check (LDPC) codes.
LDPC codes are very efficient linear block codes that can provide high transmission rates that approach the optimum channel capacity, i.e. the theoretical maximum amount of information that can be transmitted over a communication channel. In particular, non-binary LDPC codes are very efficient in providing high-spectral efficiency coding and can achieve better error-correction performance than binary LDPC codes.
Given the linearity property, any linear error correcting code can be represented by a generator matrix and a parity-check matrix. The entries of the generator and parity-check matrices belong to the algebraic structure over which the error correcting code is constructed.
The parity-check matrix defines the parity-check constraints designed to be satisfied by the codewords. In particular, LDPC codes are specified by sparse parity-check matrices comprising a number of zero entries which is much higher than the number of non-zero entries.
Decoding data encoded using linear error correcting codes can be performed based on a graph representation of the code, so-called ‘Tanner graph’, associated with the parity-check matrix of the underlying code. The graph representation of a linear error correcting code comprises two sets of nodes: a first set of nodes referred to as ‘variable nodes’ and a second set of nodes referred to as ‘check nodes’. Variable nodes and check nodes are linked together by edges. Variable nodes and check nodes form processing units. Each variable node is associated with a column of the parity-check matrix. Each check node is associated with a row of the parity-check matrix, i.e. with a parity-check equation. The connections between variable nodes and check nodes are determined by the non-zero entries of the parity-check matrix.
Iterative decoders can be used to decode data encoded using linear block error correcting codes. Given a noisy sequence of encoded symbols representing for example the output of a communication channel, an iterative decoder processes the noisy sequence during a number of iterations bringing it at each iteration closer to the original sequence of encoded symbols.
The Tanner graph representation can be used to implement iterative decoding. Accordingly, the decoding process can be performed by an iterative exchange of messages between the processing units associated with the variable nodes and check nodes via the different edges connecting them in the graph. Each variable node processing unit and check node processing unit receives input messages (check node messages and variable node messages respectively) from the corresponding connected nodes in the graph and delivers, after processing the input messages, output messages to at least one processing unit corresponding to a connected node in the graph (variable node messages and check node messages respectively). The decoding process stops either if all parity-check constraints are satisfied, returning thus the decoded codeword, or by reaching a maximum number of iterations without meeting all parity check constraints.
Passed messages between the different variable node processing units and check node processing units carry information associated with the encoded symbols. A message may comprise symbols and metrics measuring the reliability of the symbols (hereinafter referred to as the ‘reliability metric’). The reliability metric of a symbol may correspond for example to its estimated probability density function, measuring the probability that this symbol is equal to each value in the algebraic structure of construction of the code.
Early iterative decoding algorithms were designed for binary codes and apply to binary LDPC codes. They are the ‘sum-product’ algorithm (also known as ‘belief propagation’ or ‘message passing’ algorithm) and the ‘min-sum’ algorithm disclosed both in “N. Wibereg, H-A. Loeliger, and R. Kotter, Codes and Iterative Decoding on General Graphs, European Transactions on Telecommunications and Related Technologies, special issue on Turbo Coding, June 1995”. They provide near-optimal performance in terms of error decoding probability.
Iterative decoding algorithms designed for non-binary codes were inspired by the ‘sum-product’ algorithm. Exemplary iterative decoders for non-binary codes comprise the ‘q-ary sum-product’ algorithm disclosed for example in:    “M. Davey and D. MacKay, Low-density parity check codes over GF(q), IEEE Communications Letters, vol. 2, no. 6, pages 165-167, June 1998”,    “D. J. C. Mackay and M. Davey, Evaluation of Gallager Codes for Short Block Length and High Rate Applications, In Proceedings of IMA Workshop on Codes, Systems and Graphical Models, 1999”, and    “L. Barnault and D. Declercq, Fast decoding algorithm for LDPC over GF(q), In Proceedings of IEEE Information Theory Workshop, pages 70-73, April 2003”.
Some iterative decoding algorithms are based on logarithmic-scale computations for reducing the computational complexity by transforming product operations to simple summation operations. Such decoding schemes comprise:    the ‘max-log-map’ turbo codes decoder disclosed in “H. Sadjadpour, Maximum A Posteriori Decoding Algorithms For Turbo Codes, In Proceedings of SPIE, vol. 4045, 2000”,    the ‘extended min-sum’ (EMS) non-binary LDPC codes decoder disclosed in “D. Declercq and M. Fossorier, Decoding algorithms for non-binary LDPC codes over GF, IEEE Transactions on Communications, vol, 55, no. 4, pages 633-643, April 2007”;    the ‘min-max’ non-binary LDPC codes decoder disclosed in “V. Savin, Min-max decoding for non-binary LDPC codes, In Proceedings of IEEE International Symposium on Information Theory, pages 960-964, July 2008”, and    the ‘Trellis EMS decoder’ disclosed for examples in “J. O. Lacruz, F. Garcia-Herrero, J. Valls and D. Declercq, One Minimum Only Trellis Decoder for Non-Binary Low-Density Parity-Check Codes, in IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 62, no. 1, pages 177-184, January 2015” and “E. Li, F. Garcia-Herrero, D. Declercq, K. Gunnam, J. O. Lacruz and J. Valls, “Low latency T-EMS decoder for non-binary LDPC codes,” 2013 Asilomar Conference on Signals, Systems and Computers, Pacific Grove, C A, 2013, pp. 831-835”.
The EMS algorithm is based on log-domain computations of the exchanged messages between the variable node processing units and the check node processing units. As the largest complexity of the EMS algorithm is the computation performed by the check node processing units, the EMS algorithm applies a sorting and truncation of processed messages to further alleviate the computational complexity and memory requirements at check node processing units. Message sorting is performed according to an order of the reliability metrics associated with the symbols comprised in the received messages. Message truncation is performed for retaining the most reliable symbols in a given input and/or output message.
The computation of check node messages at the level of the check node processing units from the sorted and truncated input messages (i.e. variable node messages) can be performed according to various architectures. Existing architectures include “forward-backward” architectures and syndrome-based architectures.
In a “forward-backward” architecture, the computations performed by a check node processing unit are divided up into multiple serial calculations involving multiple elementary check node processing units (hereinafter referred to as ‘elementary check node processors’). Each elementary check node processor processes two or more input messages to generate an intermediate message that is subsequently used by remaining elementary check node processors, at later stages. Computed intermediate messages are sorted based on the reliability metrics associated with the decoded symbols. In addition, an elimination of redundancies is performed by each elementary check node processor to suppress messages comprising the same symbols while keeping the message comprising the most reliable of the redundant symbols. Exemplary algorithms for elementary check node processing comprise:    the ‘Bubble check’ algorithm disclosed in “E. Boutillon and L. Conde-Canencia, Bubble check: a simplified algorithm for elementary check node processing in extended min-sum non-binary LDPC decoders, Electronics Letters, vol. 46, no. 9, pp. 633-634, April 2010”, and    an improved version of the ‘Bubble check’ algorithm known as ‘L-Bubble check’ disclosed “E. Boutillon, L. Conde-Canencia, and A. Al Ghouwayel, Design of a GF(64)-LDPC Decoder based on the EMS algorithm, IEEE Transactions on Circuits and Systems, vol. 60, no. 10, pages 2644-2656, October 2013”.
The Bubble-check and L-Bubble check algorithms are based on a reduction of the search space of the best intermediate results computed by an elementary check node processor from two input messages.
In a syndrome-based architecture, a check node processing unit implements a syndrome-based decoding. The computation of check node messages from the sorted and truncated input messages requires two steps. At a first step, the check node processing unit computes a set of values termed ‘syndromes’ involving all input messages. In a second step, a decorrelation operation is performed in association with each check node message. The decorrelation operation consists of cancelling, from the computed syndromes, the contribution of the input message previously received from the variable node processing unit that is a recipient of the computed check node message. The syndrome-based architecture is disclosed in:    “P. Schlafer, N. When, M. Alles, T. Lehnigk-Emden, and E. Boutillon, Syndrome based check node processing of high order NB-LDPC decoders, In Proceedings of the International Conference on Telecommunications, pages 156-162, April 2015”;    “P. Schlafer, et al., A new Architecture for High Speed, Low Latency NB-LDPC Check Node Processing, In Proceedings of IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, August 2015”; and    “V. Rybalkin, P. Schlafer and N. Wehn, A New Architecture for High Speed, Low Latency NB-LDPC Check Node Processing for GF(256), In Proceedings of IEEE 83rd Vehicular Technology Conference (VTC Spring), Nanjing, pages 1-5, 2016”.
A syndrome-based architecture allows parallel computation, which is particularly advantageous for higher-order Galois fields. However, with such an architecture, the computational complexity is dominated by the number of computed syndromes which increases as the number of the input messages increases.
The forward-backward architecture allows a reduction of the hardware cost. However, it introduces high latency resulting in degradation in the system throughput. The syndrome-based architecture introduces high complexity mainly due to the increasing number of computed syndromes. The implementations of the syndrome-based architecture in practical decoding systems require significant computational and storage resources that are not always available. In particular, some practical implementations of this architecture are not adapted to the decoding of non-binary codes having high coding rates.
There is accordingly a need for developing more efficient and lower complexity architectures for check node processing units implemented in an EMS decoder in particular, and in any Tanner graph-based iterative decoder in general.